package 剑指offer;

/**
 * @author zhangmin
 * @create 2021-12-02 9:35
 * 位运算
 */
public class day22_561_562 {

    /**==============================================================================================================================================
     * 剑指 Offer 56 - I. 数组中数字出现的次数
     * 相同数字异或结果为0，先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
     * 在异或结果中找到任意为 1的位。根据这一位对所有的数字进行分组。在每个组内进行异或操作，得到两个数字。
     * */
    public int[] singleNumbers(int[] nums) {
        //先将所有元素异或
        int res=0;
        for (int n:nums) {
            res^=n;
        }
        //在异或的结果中找到不为0的最低位
        int index=1;
        while ((index&res)==0) index<<=1;
        //依据第index位是否为1分组，然后每组内异或，得到两个数,index的中只有一位为1
        int a=0,b=0;
        for (int n:nums) {
            if ((index&n)!=0){
                a^=n;
            }else {
                b^=n;
            }
        }
        return new int[]{a,b};
    }

    /**==============================================================================================================================================
     * 剑指 Offer 56 - II. 数组中数字出现的次数 II
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     * 考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
     * 1、状态机
     * 2、遍历统计：使用与运算获得二进制数的最右一位n1 ：n1=num&i  配合 无符号右移操作 ，可获取 num 所有位的值====只需要修改求余数值 mm ，即可实现解决 除了一个数字以外，其余数字都出现 mm 次 的通用问题。
     * */
    public int singleNumber1(int[] nums) {
        int ones=0,twos=0;
        for (int n:nums) {
            ones=ones^n&~twos;
            twos=twos^n&~ones;
        }
        return ones;
    }
    public int singleNumber(int[] nums) {
        int[] count=new int[32];
        for (int n:nums) {
            //计算n的每一位，加到count中
            for (int j = 0; j < 32; j++) {
                count[j]+=n&1;
                n>>>=1;//第j位到第j+1位
            }
        }
        int res=0,m=3;
        for (int i = 0; i < 32; i++) {
            res<<=1; // 左移 1 位
            res|=count[31-i]%m; // 恢复第 i 位的值到 res，从前向后恢复，count是从最后一位向前存的
        }
        return res;
    }
}
